package com.frx.sort.mergesort;

import java.util.Arrays;

/**
 * @author ：frx
 * @date ：Created in 2019/11/3 15:44
 * @description： 计算一个数组的逆序对  输入 : {3,7,6,2,1,8,5} 输出： 11
 * @modified By：
 * @version: ToDO
 */
public class FindReverse {

    public static void main(String[] args){
        int[] arr = {3,7,6,2,1,8,5};
        sortMerge(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
        System.out.println(num);
    }
    static int num;

    public static void sortMerge(int[] arr,int start,int end){
        if (start >= end){
            return;
        }
        int mid = start + (end - start)/2;
        sortMerge(arr,0,mid);
        sortMerge(arr,mid+1,end);
        merge(arr,start,end,mid);
    }
    public static void merge(int[] arr,int start,int end,int mid){
        int p1 = start;
        int p2 = mid + 1;
        int p = 0;
        int[] tmp = new int[end-start + 1];
        while (p1<= mid && p2 <= end){
            if (arr[p1] < arr[p2]){
                tmp[p++] = arr[p1++];
            } else {
                // 存在逆序对，计算逆序对的数量
                num += (mid - p1 + 1);
                tmp[p++] = arr[p2++];
            }
        }

        while (p1 <= mid){
            tmp[p++] = arr[p1++];
        }
        while (p2 <= end){
            tmp[p++] = arr[p2++];
        }
        // 拷贝数组
        for (int i=0;i<tmp.length;i++){
            arr[start + i] = tmp[i];
        }


    }

}
